/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/split-string
   @Language: C++
   @Datetime: 19-04-25 14:08
   */

class Solution {
	void backtrack(vector<vector<string> > &vs, vector<string> &v,
			string &str, int pos){
		if(pos>=str.length()){
			vs.push_back(v);
			return;
		}
		v.push_back(str.substr(pos,1));
		backtrack(vs,v,str,pos+1);
		if(pos+2<=str.length()){
			v.back()=str.substr(pos,2);
			backtrack(vs,v,str,pos+2);
		}
		v.pop_back();
	}
public:
	/*
	 * @param : a string to be split
	 * @return: all possible split string array
	 */
	vector<vector<string> > splitString(string& s) {
		// write your code here
		vector<vector<string> > vs;
		vector<string> v;
		backtrack(vs,v,s,0);
		return vs;
	}
};
